﻿#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996)
#include <stdio.h>
//一、算法效率
//1.1如何衡量一个算法的好坏
//从时间复杂度和空间复杂度来分析算法好坏
//
//摩尔定律：每18个月（一个半年），半导体晶体管数量会增加一倍，内存越来越便宜
//现在的cpu已经达到物理极限了，目前开辟多个处理器，也就是几核的处理器，16核什么的
//
//所以我们如今不需要再特别关注一个算法的空间复杂度
//
//2.1 时间复杂度的概念：
//算法的时间复杂度是一个函数，算法中的基本操作的执行次数，为算法的时间复杂度，因为如果要以运行时间的长短来衡量一个算法的
//好坏的话，这是不现实的，因为不同的处理器，不同的运行环境下的运行时间是不同的，所以我们用基本操作的执行次数来衡量一个算法
//的好坏，这样我们也可以脱离环境，直接来比较两个算法的好坏
//
//void func(int n)
//{
//	int count = 0;
//	for (i = 0; i < n; i++)
//	{
//		for (j = 0; j < n; j++)
//		{
//			++count;
//		}
//	}
//	for (k = 0; k < 2 * n; k++)
//	{
//		++count;
//	}
//	int m = 10;
//	while (m--)
//	{
//		++count;
//	}
//	printf("%d", count);
//	return 0;
//}
//
//上面这个算法的时间复杂度的函数式（表达式）就为：F(n)=n*n+2*n+10
//当n=10    130，当n=100   10210，当n=1000    1002010
//F(n)=n*n
//当n=10    100，当n=100   10000，当n=1000    1000000
//说明当n越大时，后面两项对表达式结果的影响越来越小
//
//所以实际中我们计算算法的时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么我们使用大O的
//渐进表示法（估算大概的次数就可以了）
//
//所以我们上面代码的时间复杂度可以表示为O(N²)（估算）
//
//2.2大O的渐进表示法
//（1）用常数1取代运行时间中的所有加法常数（一个运行次数为常数次的算法，其时间复杂度就是O(1)）不是代表算法运行一次，是
//常数次
//（2）在修改后的运行次数函数中，只保留最高阶项
//（3）如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶
//
//当一个算法，随着输入不同，时间复杂度也不同，这时，时间复杂度做悲观预期，看最坏的情况
//
//计算bubble_sort的时间复杂度
//void bubble_sort(int*a,int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i-1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//
//}
//算时间复杂度不能只去看是几层循环，而要去看他的思想

//二分查找需要在数组有序的前提下，进行查找，这个时候的效率是非常nb的


//
//斐波那契数列的递归写法完全是一个实际没用的算法，因为他的速度简直太慢了


//3.空间复杂度
//概念：空间复杂度也是一个数学函数表达式，是对一个算法在运行过程中临时占用的存储空间大小的量度
//
//空间是可以重复利用的，不累计。时间是一去不复返，累计的。

//int main()
//{
//	unsigned int begin = clock();
//	unsigned int n = 0, i = 0;
//	for (i = 0; i < 100000000; i++)
//	{
//		++n;
//	}
//	unsigned int end = clock();
//	printf("%d毫秒", end - begin);
//
//	return 0;
//}
//预期管理，如果一个算法的时间复杂度是有不同的情况的话，我们取那个最坏的情况所需的时间

//1.二分查找的时间复杂度（分析）
//假设现在我们有N个数的一个有序数列，我们要在里面查找一个数X。
//最好的情况就是，我们查找一次，就可查找出来，但现在我们要判断最坏的情况。
//什么是最坏的情况呢？
//每找一次，我们查找的数列的范围就会缩小二倍，所以N/2的次数就是我们查找的次数，就比如总共有8个数时，我们的最坏情况也就是查找3次
//所以时间复杂度就是O(logN)（将log以2为低直接写成logN就行了）

//总结：所以我在这里可以总结出来，我们的时间复杂度其实和数据的大小有关系，这个数据的大小我们用N来表示，
//所以计算次数我们只要将n带入就行，但不保证结果精确，只是因为计算机运算速度很牛逼，那些常数对计算机来说可有可无

//2.阶乘递归的时间复杂度
// 计算阶乘递归Fac的时间复杂度？
//long long Fac(size_t N)
//{
//	if (1 == N)
//		return 1;
//
//	return Fac(N - 1) * N;
//}
//我们递归了N次，O(N)就是我们的时间复杂度表达式

//long long Fac(size_t N)
//{
//	if (1 == N)
//		return 1;
//	for (i = 0; i < N; i++)//这个N从N会一直变到2，但他的次数是以等差数列的形式，一直变小
//	{
//		;
//	}
//	return Fac(N - 1) * N;
//}
//值得注意的是，我们这里的次数是一个等差数列，就是N一直加到1，N*(N+1)/2次，所以保留最高阶就是N²次

//不要管那些边边角角的次数，你直接算个大概就行了，那么精确你是闹甚呀，三瓜两枣不重要，忽略次要矛盾，抓住主要矛盾

//本质上我们来看的是这个算法内容的执行次数，递归次数又不算内容执行次数，所以我们上面代码的时间复杂度是等差数列.

//这里最后一个总结就是，我们递归的时间复杂度的计算其实就是：每次递归调用的执行次数累加,就比如我们上面的两个代码实例，
//第一个中每次递归执行次数我们都可以看成是常数次，所以就是n个常数累加起来，那么时间复杂度就是O(N)
//第二个中每次递归的执行次数是变化的，第一次是N，最后一次是1，那么和就是个等差数列，所以去掉边边角角之后，时间复杂度是O(N²)


//实例八：
// 计算斐波那契递归Fib的时间复杂度？
//long long Fib(size_t N)
//{
//	if (N < 3)
//		return 1;
//
//	return Fib(N - 1) + Fib(N - 2);
//}

//空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
//注意：函数运行时所需要的栈空间（函数参数，局部变量，一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过
//函数在运行时侯显示申请的额外空间（记住是额外空间）来确定.空间复杂度算的是变量的个数

//1.计算空间复杂度
//void Func4(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 100; ++k)//count和k我们都需要开辟空间存储，但不管有多少个，他都是O(1)常数个
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 2.计算BubbleSort的空间复杂度？
//void BubbleSort(int* a, int n)
//{
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}
//在这个算法里面总共开辟了3个变量，所以空间复杂度还是O(1)

// 3.计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
//long long* Fibonacci(size_t n)
//{
//	if (n == 0)
//		return NULL;
//
//	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
//	//这里动态开辟n+1个大小为long long的空间，我们再抹去边边角角的常数个空间大小，所以我们的空间复杂度就是O(n)
//	fibArray[0] = 0;
//	fibArray[1] = 1;
//	for (int i = 2; i <= n; ++i)
//	{
//		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
//	}
//	return fibArray;
//}

// 4.计算阶乘递归Fac的空间复杂度？
//long long Fac(size_t N)
//{
//	if (N == 0)
//		return 1;
//
//	return Fac(N - 1) * N;
//}
//这里的空间复杂度就是O(N),道理非常简单，我们每次调用函数都要开辟栈帧，因为从N开辟到1，所以总共开辟了N个栈帧
//每个栈帧使用了常数个空间，所以我们抹去边边角角，开辟栈帧得个数就是我们的空间复杂度。

//所以这里我们也可以总结一下，递归空间复杂度的计算方法就是，每次递归调用所建立的栈帧中变量的个数累加得来的。
//（正因为我们每次递归调用建立的栈帧中变量个数是常数个，所以我们的空间复杂度就正好是递归调用的次数了，如果每次变量个数是
//n个，那我们的空间复杂度就是O(n²)）



// 大总结：这里我们最后总结一下，时间复杂度和空间复杂度的计算方法：
//1.时间复杂度计算的是算法中基本操作的执行次数的总和，递归情况下就是：每次递归调用的执行次数的累加
//2.空间复杂度计算的是算法中变量的个数，递归情况下就是：每次递归调用的变量个数的累加
//（对空间复杂度进行额外的补充说明，空间空间，算的是我们空间中变量的个数的累加，无论是堆区还是栈区，
//我们都要算其中变量个数的累加）有多少个空间，我们就得计算多少次里面变量的个数，虽然递归中变量没有创建，
//但是它消耗空间了呀，这就算常数次

//面试题1：消失的数字
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//要求：提供尽可能多的思路，用复杂度分析，然后实现最优的思路
//
//思路一：求和相减
//我们把1到n的数字加起来减去数组里面元素的和，得到的结果就是，数组里面缺失的数字
//思路二：qsort排序
//排序之后，去比较后一个元素是不是比前一个元素大1，如果大1，继续往后遍历，直到找出大2的那个数字，然后把这个数字-1，就可得到
//我们消失的数字了
//思路三：异或
//我们先开辟一个从0到n完整的数组，然后用0去异或这个完整数组的所有元素，我们在用最后的结果去异或缺失数字所在的数组的每个元素
//最后得到的结果就是我们消失的数字
//原因解释：我们都知道这两个数组唯一的差别就是，除消失的数字之外，其他数字在两个数组中都是存在的，那么只要将这两个数组元素混在一块
//异或之后，出现两次的数字，异或结果就会为0，而0去和出现一次的数字异或，那么结果正好就是这个消失的数字,值得注意的是
// 我们的异或其实是满足交换律的，不是一定有顺序才能异或
//空间复杂度是O(N)，如果我们不开辟数组，那么空间复杂度就是O(1)，常数个变量，因为我们没有额外开辟空间

//代码实现：
//方法一：异或的方法
//int missingNumber(int* nums, int numsSize) {
//    int k = numsSize;
//    int x = 0;
//    int i = 0;
//    for (i = 0; i < k; i++)
//    {
//        x ^= nums[i];
//    }
//    for (i = 0; i < k + 1; i++)
//    {
//        x ^= i;
//    }
//
//    return x;
//}
//方法二：先作和再做差的方法
//int missingNumber(int* nums, int numsSize) {
//    
//    int n = numsSize;
//    int sum = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        sum += nums[i];
//    }
//    return n * (n + 1) / 2 - sum;
//    
//}


//面试题2：旋转数组
//方法一：使用额外的数组
//void rotate(int* nums, int numsSize, int k) {
//	int newarr[numsSize];//不初始化也OK
//	for (i = 0; i < numsSize; i++)
//	{
//		newarr[(i + k) % numsSize] = nums[i];//这里面取余这一步是真牛逼，属实佩服了，好家伙。
//	}
//	for (i = 0; i < numsSize; i++)
//	{
//		nums[i] = newarr[i];
//	}
//}
//时间复杂度：O(N)   N为数组的长度，
//空间复杂度：O(N)   数组大小未知也就是空间大小未知，所以我们的空间复杂度就是O(N)

//方法二：数组翻转(先翻转整体，再翻转两次局部)
//void swap(int* a, int* b) {
//    int t = *a;
//    *a = *b, * b = t;
//}
//void reverse(int* nums, int start, int end) {
//    while (start < end) {
//        swap(&nums[start], &nums[end]);
//        start += 1;
//        end -= 1;
//    }
//}
//void rotate(int* nums, int numsSize, int k) {
//    k %= numsSize;
//    reverse(nums, 0, numsSize - 1);
//    reverse(nums, 0, k - 1);
//    reverse(nums, k, numsSize - 1);
//}
//方法三：错误的环状替换（烧脑）,最大公约数法，有使用前提（最大公约数不能是1）
//void rotate(int* nums, int numsSize, int k) {
//	int a = 0;
//	
//	while ((a+k)%6!=0)
//	{
//		int tmp1 = nums[a % numsSize];
//		int tmp2 = nums[(a + k)%numsSize];
//		nums[(a + 2*k) % numsSize] = tmp2;
//		nums[(a + k) % numsSize] = tmp1;
//		a++;
//
//	}
//
//}
//方法四：遍历法
void rotate(int* nums, int numsSize, int k) {
	for (int i = 0; i < k; i++)//循环我们的k次，进行k次的元素翻转
	{
		int previous = nums[numsSize - 1];
		for (int j = 0; j < numsSize; j++)//每一次的翻转，我们数组元素都会被移动数组元素大小的次数
		{	int temp = nums[j];
			nums[j] = previous;//我们在改变数组某个下标的内容之前，先去把这个下标内容存起来防止他丢失
			previous = temp;//然后我们直接把暂存的下标中内容的值，存到我们下一次要给数组赋值的局部变量里面
		}
	}
	//这算法简直太他妈牛逼了，跟以往的交换元素完全不同，我佩服的五体投地，卧槽
}
void rotate(int* nums, int numsSize, int k) {
	for (int i = 0; i < k; i++)
	{
		int tmp = nums[numsSize - 1];
		for (int j = numsSize - 1; j > 0; j--)
		{
			nums[j] = nums[j - 1];
		}
		nums[0] = tmp;
	}
	
}

//最大公约数：两个数都能约的最大数，16和12都能约1，2，4，然而4是最大的公约数
//最小公倍数：两个数扩大倍数之后相等的数，即使a的倍数也是b的倍数，48是16的倍数也是12的倍数，而且48是最小的公倍数，
//16*12/4就是最小公倍数
















































































































